{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Poor Pigs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: poorPigs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可怜的小猪"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有<code> buckets</code> 桶液体，其中 <strong>正好有一桶</strong>&nbsp;含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有&nbsp;<code>minutesToTest</code> 分钟时间来确定哪桶液体是有毒的。</p>\n",
    "\n",
    "<p>喂猪的规则如下：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>选择若干活猪进行喂养</li>\n",
    "\t<li>可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。</li>\n",
    "\t<li>小猪喝完水后，必须有 <code>minutesToDie</code> 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。</li>\n",
    "\t<li>过了 <code>minutesToDie</code> 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。</li>\n",
    "\t<li>重复这一过程，直到时间用完。</li>\n",
    "</ol>\n",
    "\n",
    "<p>给你桶的数目 <code>buckets</code> ，<code>minutesToDie</code> 和 <code>minutesToTest</code> ，返回&nbsp;<em>在规定时间内判断哪个桶有毒所需的 <strong>最小</strong> 猪数</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>buckets = 1000, minutesToDie = 15, minutesToTest = 60\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>buckets = 4, minutesToDie = 15, minutesToTest = 15\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>buckets = 4, minutesToDie = 15, minutesToTest = 30\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= buckets &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;minutesToDie &lt;=&nbsp;minutesToTest &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [poor-pigs](https://leetcode.cn/problems/poor-pigs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [poor-pigs](https://leetcode.cn/problems/poor-pigs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n15\\n15', '4\\n15\\n30']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        cnt = 0\n",
    "        while (minutesToTest // minutesToDie + 1) ** cnt < buckets:\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return ceil(log(buckets, minutesToTest // minutesToDie+1)-0.001)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return ceil(log2(buckets) / log2(minutesToTest // minutesToDie + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\r\n",
    "        times = minutesToTest // minutesToDie # 測試次數\r\n",
    "        base = times + 1 # 每頭豬可以測試的桶數\r\n",
    "        # base ^ ans >= buckets\r\n",
    "        # ans >= log(buckets) / log(base)\r\n",
    "        return math.ceil(math.log(buckets) / math.log(base) - 1e-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        n = minutesToTest // minutesToDie\n",
    "        return int(ceil(log(buckets) / log(n+1) - 1e-6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(pigs, t):\n",
    "    if t == 0 or pigs == 0:\n",
    "        return 1\n",
    "    if pigs == 1:\n",
    "        return t + 1\n",
    "    \n",
    "    res = 0\n",
    "    for i in range(pigs+1):\n",
    "        res += comb(pigs, i) * dfs(i, t-1)\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        cnt = minutesToTest // minutesToDie\n",
    "        ans = 0\n",
    "        while dfs(ans, cnt) < buckets:\n",
    "            ans += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        # 计算可以进行的测试轮数\n",
    "        rounds = minutesToTest // minutesToDie\n",
    "        # 每只猪可以提供的信息量是状态数的对数\n",
    "        pigs = 0\n",
    "        # 当前猪的数量能区分的最大桶数\n",
    "        while (rounds + 1) ** pigs < buckets:\n",
    "            pigs += 1\n",
    "        return pigs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        states = minutesToTest // minutesToDie + 1\n",
    "        return ceil(log(buckets) / log(states) - 1e-5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        k = int(minutesToTest / minutesToDie + 1)\n",
    "        return ceil(log(buckets) / log(k) - 1e-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return ceil(log(buckets - .4, minutesToTest // minutesToDie + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        lines = minutesToTest//minutesToDie+1\n",
    "        for i in range(0, 10000000):\n",
    "            if lines**i >=buckets:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        lines = minutesToTest//minutesToDie+1\n",
    "        for i in range(0, 11):\n",
    "            if lines**i >=buckets:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return math.ceil(math.log(buckets, (minutesToTest // minutesToDie + 1))-1e-7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        pigs = 0\n",
    "        while (minutesToTest // minutesToDie + 1) ** pigs < buckets:\n",
    "            pigs += 1\n",
    "        return pigs\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        rounds = minutesToTest // minutesToDie\n",
    "        pig = math.log(buckets,(rounds+1))\n",
    "        print(rounds, pig)\n",
    "        return math.ceil(pig - 0.00001)\n",
    "\n",
    "'''\n",
    "round   pig     bucket\n",
    "1       1       2\n",
    "1       2       4\n",
    "1       3       8\n",
    "2       1       3\n",
    "2       2       9\n",
    "\n",
    "bucket=(round+1)^pig\n",
    "pig=\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return ceil(log(buckets, minutesToTest//minutesToDie + 1)-1e-5)\n",
    "\n",
    "# class Solution:\n",
    "#     def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "#         states = minutesToTest // minutesToDie + 1\n",
    "#         return ceil(log(buckets) / log(states) - 1e-5)\n",
    "\n",
    "\n",
    "\n",
    "# 特别经典的一道题，1024个桶里，有一个有毒，十个小白鼠可以做测试，怎么一次找到有毒的那个\n",
    "# 将0~1023写成二进制，最多是十位，每个小白鼠喝所有某一位为1的（一鼠一位）\n",
    "# 最终要找的那个就是所有死的小白鼠的位为1，其他位为0\n",
    "# 我们知道十只小白鼠一次可以试出2^10个桶，如果是两次呢？\n",
    "# 其实两次可以看成三进制，每个小白鼠可以在两轮内试出某一位是0还是1还是2\n",
    "# 第一次死就是那一位为1，第二次是那一次为2，没死就是那一位为0\n",
    "# 这样来看的话，\n",
    "# x轮就该转换成(x+1)进制, 我们要找buckets在x+1进制下是几位，就是我们至少需要的小白鼠个数了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return math.ceil(math.log(buckets)/math.log(minutesToTest // minutesToDie + 1) - 1e-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        pigs = 0\n",
    "        while (minutesToTest // minutesToDie + 1) ** pigs < buckets:\n",
    "            pigs += 1\n",
    "        return pigs\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        times = minutesToTest/minutesToDie+1\n",
    "        return math.ceil(math.log(buckets) / math.log(times) -1e-5)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        # 计算每头猪可以测试的状态数（包括不喝、喝毒药、喝正常药水的状态）。\n",
    "        states = minutesToTest // minutesToDie + 1\n",
    "        \n",
    "        # 使用对数函数计算需要多少头猪来测试所有的桶子。\n",
    "        # 这里使用对数底数无关紧要，通常使用自然对数（底数e）或者常用对数（底数10）都可以。\n",
    "        # 由于底数不同，所以需要对结果稍微调整，-1e-5 是一个微小的修正值。\n",
    "        return ceil(log(buckets) / log(states) - 1e-5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        \n",
    "        # n只\\U0001f416能管 (测试次数+1) ^ n只诸\n",
    "        \n",
    "        together = minutesToTest // minutesToDie\n",
    "\n",
    "        return ceil(log(buckets) / (log(together + 1)) - 1e-5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        number= minutesToTest//minutesToDie\n",
    "        i=0\n",
    "        while (number+1)**i<buckets:\n",
    "            i+=1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return ceil(log(buckets, minutesToTest // minutesToDie+1)-0.001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return ceil(log(buckets, minutesToTest // minutesToDie+1)-0.001)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        base = minutesToTest//minutesToDie+1\n",
    "        num = 0\n",
    "        while base**num<buckets:\n",
    "            num+=1\n",
    "        return num\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        n = minutesToTest // minutesToDie + 1\n",
    "        pigs = 0\n",
    "        while n ** pigs <  buckets:\n",
    "            pigs += 1\n",
    "        return pigs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        # return math.ceil(math.log(buckets,minutesToTest//minutesToDie+1))\n",
    "        if buckets==1:return 0\n",
    "        base=minutesToTest//minutesToDie+1\n",
    "        ct=1\n",
    "        states=ct*base\n",
    "        while states<buckets:\n",
    "            states*=base\n",
    "            ct+=1\n",
    "        return ct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        t=math.floor((minutesToTest/minutesToDie)+1)\n",
    "        n=0\n",
    "        sum=1\n",
    "        while sum<buckets: \n",
    "            sum*=t\n",
    "            n+=1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        k = int(minutesToTest / minutesToDie + 1)\n",
    "        return ceil(log(buckets) / log(k) - 1e-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        pigs = 0\n",
    "        while (minutesToTest // minutesToDie + 1) ** pigs <buckets:\n",
    "            pigs += 1\n",
    "        return pigs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        cnt = minutesToTest // minutesToDie + 1\n",
    "        ans = 0\n",
    "        dfs = 1\n",
    "        while dfs < buckets:\n",
    "            ans += 1\n",
    "            dfs *= cnt \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        # 可以测试 k = minutesToTest // minutesToDie 次\n",
    "        # 每只猪有 k + 1 种状态 (第一次测试死, 第二次测试死, ..., 第 k 次测试死, 存活)\n",
    "        # 相当于 k + 1 进制数\n",
    "        # n 只猪相当于 n 位 k + 1 进制数, 有 (k + 1) ^ n 种状态\n",
    "        # 求 (k + 1) ^ n >= buckets --> n = ceil(log(buckets, k + 1))\n",
    "        k = minutesToTest // minutesToDie\n",
    "        return math.ceil(math.log2(buckets) / math.log2(k + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        pigs = 0\n",
    "        while (minutesToTest // minutesToDie + 1) ** pigs < buckets:\n",
    "            pigs += 1\n",
    "        return pigs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        pigs = 0\n",
    "        while (minutesToTest // minutesToDie + 1) ** pigs < buckets:\n",
    "            pigs += 1\n",
    "        return pigs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        states = minutesToTest // minutesToDie + 1\n",
    "        return ceil(log(buckets) / log(states) - 1e-5)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        state = minutesToTest//minutesToDie+1\n",
    "        return ceil(log(buckets)/log(state)-1e-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil, log\r\n",
    "class Solution:\r\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\r\n",
    "        return ceil(log(buckets, minutesToTest // minutesToDie + 1) - 1e-12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        pigs = 0\n",
    "        while (minutesToTest // minutesToDie + 1) ** pigs < buckets:\n",
    "            pigs += 1\n",
    "        return pigs\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import log, ceil\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        xx = minutesToTest // minutesToDie + 1\n",
    "        return ceil(log(buckets,xx)-0.0001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        states = minutesToTest // minutesToDie + 1\n",
    "        return ceil(log(buckets) / log(states) - 1e-5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        lines = minutesToTest//minutesToDie+1\n",
    "        for i in range(0, 10000):\n",
    "            if lines**i >=buckets:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        k=int(minutesToTest/minutesToDie)\n",
    "        def c(n,k):\n",
    "            def jie(x):\n",
    "                if x==0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return x*jie(x-1)\n",
    "            return jie(n)/(jie(k)*jie(n-k))\n",
    "        def f(p,k):\n",
    "            if k==1:\n",
    "                return 2**p\n",
    "            if p==0:\n",
    "                return 1\n",
    "            if p==1:\n",
    "                return k+1\n",
    "            else:\n",
    "                return sum([c(p,n)*f(p-n,k-1) for n in range(p+1)])\n",
    "        for i in range(6):\n",
    "            if f(i,k)>=buckets:\n",
    "                return i\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        K = minutesToTest // minutesToDie + 1\n",
    "        f = [[0] * (buckets + 1) for _ in range(K)]\n",
    "        for i in range(K): f[i][0] = 1\n",
    "        for j in range(buckets): f[0][j] = 1\n",
    "        if buckets == 1: return 0\n",
    "        for j in range(1, buckets + 1):\n",
    "            for i in range(1, K):\n",
    "                for k in range(j + 1):\n",
    "                    f[i][j] += comb(j, k) * f[i - 1][k]\n",
    "                if f[i][j] >= buckets:\n",
    "                    return j\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        n = minutesToTest // minutesToDie + 1\n",
    "        return math.ceil(math.log(buckets) / math.log(n) - 1e-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        states = minutesToTest // minutesToDie + 1\n",
    "        return ceil(log(buckets) / log(states) - 1e-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(pigs, t):\n",
    "    if t == 0:\n",
    "        return 1\n",
    "    \n",
    "    res = 0\n",
    "    for i in range(pigs+1):\n",
    "        res += comb(pigs, i) * dfs(i, t-1)\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        cnt = minutesToTest // minutesToDie\n",
    "        ans = 0\n",
    "        while dfs(ans, cnt) < buckets:\n",
    "            ans += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        \n",
    "        # n只\\U0001f416能管 (测试次数+1) ^ n只诸\n",
    "        \n",
    "        together = minutesToTest // minutesToDie\n",
    "\n",
    "        return ceil(log(buckets) / (log(together + 1)) - 1e-5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from decimal import Decimal\r\n",
    "from decimal import getcontext\r\n",
    "getcontext().prec = 10000\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\r\n",
    "        # base ^ ans >= buckets\r\n",
    "        # ans >= log(buckets) / log(base)\r\n",
    "        times = minutesToTest // minutesToDie # 測試次數\r\n",
    "        base = times + 1 # 每頭豬可以測試的桶數\r\n",
    "        # log的精準度問題\r\n",
    "        # print(math.log(buckets), math.log(base), math.log(buckets) / math.log(base))\r\n",
    "        # print(math.log10(buckets), math.log10(base), math.log10(buckets) / math.log10(base))\r\n",
    "        return math.ceil(math.log10(buckets) / math.log10(base))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        states = minutesToTest // minutesToDie + 1\n",
    "        return ceil(log(buckets) / log(states) - 0.001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        cnt = 0\n",
    "        while(minutesToTest / minutesToDie + 1) ** cnt < buckets:\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        pigs = 0\n",
    "        while (minutesToTest // minutesToDie + 1) ** pigs < buckets:\n",
    "            pigs += 1\n",
    "        return pigs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\r\n",
    "        # base ^ ans >= buckets\r\n",
    "        # ans >= log(buckets) / log(base)\r\n",
    "        times = minutesToTest // minutesToDie # 測試次數\r\n",
    "        base = times + 1 # 每頭豬可以測試的桶數\r\n",
    "        # log的精準度問題\r\n",
    "        # print(math.log(buckets), math.log(base), math.log(buckets) / math.log(base))\r\n",
    "        # print(math.log10(buckets), math.log10(base), math.log10(buckets) / math.log10(base))\r\n",
    "        return math.ceil(math.log10(buckets) / math.log10(base))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "\n",
    "        # answer = 0\n",
    "        # while (minutesToTest // minutesToDie + 1) ** answer < buckets:\n",
    "        #     answer += 1\n",
    "\n",
    "        # return answer \n",
    "\n",
    "        # k = minutesToTest // minutesToDie # 每只小猪测试次数\n",
    "        # return math.ceil(math.log(buckets) / math.log(k + 1) - 1e-5)\n",
    "\n",
    "        answer = 0\n",
    "        k = minutesToTest // minutesToDie + 1\n",
    "        while (k ** answer < buckets): answer += 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        cnt = 0\n",
    "        while(minutesToTest // minutesToDie + 1) ** cnt < buckets:\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        lines = minutesToTest//minutesToDie+1\n",
    "        for i in range(0, 100):\n",
    "            if lines**i >=buckets:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        @ cache\n",
    "        def dfs(pg, rd):\n",
    "            if rd == 1:\n",
    "                return 2 ** pg\n",
    "            ans = 0\n",
    "            if rd > 1:\n",
    "                for i in range(2 ** pg):\n",
    "                    ans += dfs(pg - i.bit_count(), rd - 1)\n",
    "            return ans\n",
    "        n = minutesToTest // minutesToDie\n",
    "        for i in range(buckets):\n",
    "            if dfs(i, n) >= buckets:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        return math.ceil(math.log2(buckets)/math.log2(minutesToTest//minutesToDie+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\r\n",
    "        import math\r\n",
    "        return math.ceil(math.log2(buckets)/math.log2(minutesToTest//minutesToDie+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        iter_num = int(minutesToTest / minutesToDie)\n",
    "        dp = [[0 for _ in range(iter_num + 1)] for _ in range(buckets)]\n",
    "        for i in range(buckets):\n",
    "            dp[i][0] = 1\n",
    "        for j in range(iter_num + 1):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, buckets):\n",
    "            for j in range(1, iter_num + 1):\n",
    "                for k in range(i + 1):\n",
    "                    dp[i][j] += dp[k][j-1] * math.comb(i, k)\n",
    "                if dp[i][j] >= buckets:\n",
    "                    return i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        if buckets==1:\n",
    "            return 0\n",
    "        combinations = [[0] * (buckets + 1) for _ in range(buckets + 1)]\n",
    "        combinations[0][0]=1\n",
    "        iterations = minutesToTest // minutesToDie\n",
    "        f = [[1] * (iterations + 1)] + [[1] + [0] * iterations for _ in range(buckets - 1)]\n",
    "        for i in range(1, buckets):\n",
    "            combinations[i][0] = 1\n",
    "            for j in range(1, i):\n",
    "                combinations[i][j] = combinations[i - 1][j - 1] + combinations[i - 1][j]\n",
    "            combinations[i][i] = 1\n",
    "            for j in range(1,iterations+1):\n",
    "                for k in range(i+1):\n",
    "                    f[i][j]+=f[k][j-1]*combinations[i][i-k]\n",
    "            if f[i][iterations] >= buckets:\n",
    "                return i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        if buckets==1:\n",
    "            return 0\n",
    "        combinations = [[0] * (buckets + 1) for _ in range(buckets + 1)]\n",
    "        combinations[0][0]=1\n",
    "        iterations = minutesToTest // minutesToDie\n",
    "        f = [[1] * (iterations + 1)] + [[1] + [0] * iterations for _ in range(buckets - 1)]\n",
    "        for i in range(1, buckets):\n",
    "            combinations[i][0] = 1\n",
    "            for j in range(1, i):\n",
    "                combinations[i][j] = combinations[i - 1][j - 1] + combinations[i - 1][j]\n",
    "            combinations[i][i] = 1\n",
    "            for j in range(1,iterations+1):\n",
    "                for k in range(i+1):\n",
    "                    f[i][j]+=f[k][j-1]*combinations[i][k]\n",
    "            if f[i][iterations] >= buckets:\n",
    "                return i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:\n",
    "        if buckets == 1:\n",
    "            return 0\n",
    "        combinations = [[0] * (buckets + 1) for _ in range(buckets + 1)]\n",
    "        combinations[0][0] = 1\n",
    "        iterations = minutesToTest // minutesToDie\n",
    "        f = [[1] * (iterations + 1)] + [[1] + [0] * iterations for _ in range(buckets - 1)]\n",
    "        for i in range(1, buckets):\n",
    "            combinations[i][0] = 1\n",
    "            for j in range(1, i):\n",
    "                combinations[i][j] = combinations[i - 1][j - 1] + combinations[i - 1][j]\n",
    "            combinations[i][i] = 1\n",
    "            for j in range(1, iterations + 1):\n",
    "                for k in range(i + 1):\n",
    "                    f[i][j] += f[k][j - 1] * combinations[i][i - k]\n",
    "            if f[i][iterations] >= buckets:\n",
    "                return i\n",
    "        return 0\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
